//048. 自身的幂
//        数列 1^1 + 2^2 + 3^3 +...+ 10^10 = 10305071317
//        求 1^1 + 2^2 + 3^3 +...+ 1000^1000的最后十位数。
//        答案：9110846700


import java.math.BigInteger;

public class Week048 {
    static final int N = 10;
    static int[] ans = new int[N];
    static int[] cur = new int[N];

    //cur为返回值,返回n的n次幂
    static void pow(int n) {
        int i, t, j;
        for (i = 0, t = n; t != 0; t /= 10, ++i) cur[i] = t % 10;//将n分解成数组
        for (; i < N; ++i) cur[i] = 0;//多的位置0
        for (i = 1; i < n; ++i) {
            for (j = 0, t = 0; j < N; ++j) {
                cur[j] = cur[j] * n + t;
                t = cur[j] / 10;
                cur[j] %= 10;
            }
        }
    }

    //使ans+=cur
    static void add() {
        for (int i = 0, temp = 0; i < N; ++i) {
            ans[i] += cur[i] + temp;//对应位相加，并加上进位
            temp = ans[i] / 10;//求出进位
            ans[i] %= 10;//保留个位
        }
    }

    static void run() {
//        BigInteger ans = BigInteger.ONE;
//        for (int i = 2; i <= 1000; ++i) {
//            ans = ans.add(BigInteger.valueOf(i).pow(i));
//        }
//        String Ans = ans.toString();
//        System.out.println(Ans.substring(Ans.length() - 10));

        final int n = 1000;
        for (int i = 1; i <= n; ++i) {
            pow(i);
            add();
        }
        for (int i = N - 1; i >= 0; --i) {
            System.out.print(ans[i]);
        }
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        run();
        System.out.println("\n程序运行时间：" + (System.currentTimeMillis() - startTime) + "ms.");
    }
}
